Structure of the Book

本书结构

This book evolved from classes given by the author over many years to students at the College of William & Mary, Virginia Tech, and the United States Naval Academy. I have divided the book into 8 chapters and 54 sections, including three review sections. Each section corresponds very closely to the material I cover in a single 50-minute lecture. Sections are further divided into many short subsections, so that my suggested pacing can readily be adapted for classes that meet for 75 minutes, 80 minutes, or other time intervals. If the instructor omits all sections and topics designated as “optional,” it should be just possible to finish all of the core material in a semester class that meets for 2250 minutes (typically forty-five 50-minute meetings or thirty 75-minute meetings). More suggestions for possible course designs appear below.

本书源于作者多年来在威廉玛丽学院、弗吉尼亚理工大学和美国海军学院为学生讲授的课程。全书分为8章54节，其中包括3个复习节。每个节的内容都与我50分钟的单次授课内容高度吻合。每个节又细分为许多小节，因此我建议的教学进度可以根据75分钟、80分钟或其他课时的时长灵活调整。如果教师省略所有标有“可选”的章节和主题，那么在一个学期共计2250分钟（通常为45次50分钟的课或30次75分钟的课）的课程中，应该刚好可以完成所有核心内容的讲授。更多课程设计建议请参见下文。

I have tried to capture the best features of live mathematics lectures in the pages of this book. New material is presented to beginning students in small chunks that are easier to digest in a single reading or class meeting. The book maintains the friendly conversational style of a classroom presentation, without relinquishing the necessary level of precision and rigor. Throughout this text, you will find the personal pronouns “I” (the author), “you” (the reader), and “we” (the author and the reader, working together), reminding us that teaching and learning are fundamentally human activities. Teaching this material effectively can be as difficult as learning it, and new instructors are often unsure how much time to spend on the fundamentals of logic and proof techniques. The organization of this book shows at a glance how one experienced teacher of proofs allocates time among the various core topics. The text develops mathematical ideas through a continual cycle of examples, theorems, proofs, summaries, and reviews. A new concept may be introduced briefly via an example near the end of one section, then examined in detail in the next section, then recalled as needed in later sections. Every section ends with an immediate review of the key points just covered, and three review sections give detailed summaries of each major section of the book. The essential core material is supplemented by more advanced topics that appear in clearly labeled optional sections.

我力求在本书中捕捉到现场数学讲座的精华。本书将新知识以小块形式呈现给初学者，便于他们在一次阅读或课堂学习中消化吸收。本书保持了课堂讲解的友好对话风格，同时又不失必要的精确性和严谨性。贯穿全书，你会发现“我”（作者）、“你”（读者）和“我们”（作者和读者共同学习）这三个人称代词，提醒我们教与学本质上都是人类活动。有效地教授这些内容与学习它们一样困难，新教师常常不确定应该花多少时间讲解逻辑和证明技巧的基础知识。本书的结构清晰地展示了一位经验丰富的证明教师是如何在各个核心主题之间分配时间的。本书通过例题、定理、证明、总结和回顾的循环，逐步构建数学概念。新概念可能会在某一章节的结尾通过一个例子简要介绍，然后在下一章节中进行详细探讨，并在后续章节中根据需要再次提及。每节结尾都会立即回顾刚刚讨论的关键点，此外还有三个复习章节，分别对本书的每个主要章节进行详细总结。除了核心内容之外，本书还补充了一些更高级的主题，这些主题出现在清晰标注的选读章节中。

Contents of the Book

本书内容

Here is a detailed list of the topics covered in each chapter of the book:

以下是本书各章节涵盖的主题详细列表：

1. Logic: propositions, logical connectives (NOT, AND, OR, XOR, IF, IFF), truth tables, logical equivalence, tautologies, contradictions, universal and existential quantifiers, translating and denying complex logical statements, uniqueness.
   逻辑：命题、逻辑连接词（非、与、或、异或、如果、如果）、真值表、逻辑等价、重言式、矛盾式、全称量词和存在量词、翻译和否定复杂的逻辑语句、唯一性。
2. Proofs: ingredients in mathematical theories (definitions, axioms, inference rules, theorems, proofs), proof by example, direct proof, contrapositive proof, contradiction proof, proof by cases, generic-element proofs, proofs involving multiple quantifiers.
   证明：数学理论的组成部分（定义、公理、推理规则、定理、证明），举例证明、直接证明、逆否命题证明、矛盾证明、分情况证明、通用元素证明、涉及多个量词的证明。
3. Set Theory: set operations (union, intersection, set difference), subset proofs, set equality proofs, circle proofs, chain proofs, power sets, ordered pairs, product sets, unions and intersections of indexed collections.
   集合论：集合运算（并集、交集、差集）、子集证明、集合相等证明、圆证明、链证明、幂集、有序对、乘积集、索引集合的并集和交集。
4. Integers: recursive definitions, ordinary induction proofs, induction starting anywhere, backwards induction, strong induction, integer division with remainder, greatest common divisors, Euclid’s GCD algorithm, primes, existence and uniqueness of prime factorizations.
   整数：递归定义、普通归纳证明、任意起始归纳、逆归纳、强归纳、带余数的整数除法、最大公约数、欧几里得最大公约数算法、素数、素数分解的存在性和唯一性。
5. Relations and Functions: relations, images, inverse of a relation, identity relation, composition of relations, formal definition of a function, function equality, operations on functions (pointwise operations, composition, restriction), direct images, preimages, injections, surjections, bijections, inverse functions.
   关系与函数：关系、像、关系的逆、恒等关系、关系的复合、函数的形式定义、函数相等性、函数运算（逐点运算、复合、限制）、直接像、原像、单射、满射、双射、反函数。
6. Equivalence Relations and Partial Orders: reflexivity, symmetry, transitivity, equivalence relations, congruence modulo n , equivalence classes, set partitions, antisymmetry, partial orders, well-ordered sets.
   等价关系和偏序：自反性、对称性、传递性、等价关系、模 n 同余、等价类、集合划分、反对称性、偏序、良序集。
7. Cardinality: finite sets, basic counting rules, countably infinite sets, countable sets, theorems on countability, uncountable sets, Cantor’s Theorem.
   基数：有限集、基本计数规则、可数无限集、可数集、可数性定理、不可数集、康托尔定理。
8. Real Numbers (Optional): ordered field axioms for ℝ, algebraic properties, formal definition of ℕ and ℤ and ℚ, ordering properties, absolute value, distance, Least Upper Bound Axiom and its consequences (Archimedean ordering of ℝ, density of ℚ in ℝ, existence of real square roots, Nested Interval Theorem).
   实数（可选）：ℝ 的有序域公理、代数性质、ℕ、ℤ 和 ℚ 的形式定义、排序性质、绝对值、距离、最小上界公理及其推论（ℝ 的阿基米德排序、ℚ 在 ℝ 中的密度、实数平方根的存在性、嵌套区间定理）。

Possible Course Designs

可能的课程设计

A standard three-credit (2250 minute) proofs class could cover most of the topics in Chapters 1 through 7 , which are essential for further study of advanced mathematics. When pressed for time, I have sometimes omitted or condensed the material on cardinality ( Chapter 7 ) or prime factorizations (last half of Chapter 4 ). Many variations of the standard course are also feasible. Instructors wishing to preview ideas from abstract algebra could supplement the standard core with the following optional topics:

一门标准的三学分（2250分钟）证明课程可以涵盖第1章至第7章的大部分内容，这些内容对于进一步学习高等数学至关重要。如果时间紧迫，我有时会省略或精简关于基数（第7章）或质因数分解（第4章后半部分）的内容。标准课程还有许多其他变体。希望预先介绍抽象代数概念的教师可以在标准核心课程之外，补充以下可选主题：

• the group axioms (end of Section 2.1 );
  群公理（第 2.1 节末尾）；
• unique factorization properties for ℤ and ℚ (last four sections of Chapter 4 );
  ℤ 和 ℚ 的唯一因式分解性质（第 4 章最后四节）；
• formal construction of the integers mod n and the rational numbers using equivalence relations ( Section 6.6 );
  利用等价关系对模 n 的整数和有理数进行正式构造（第 6.6 节）；
• algebraic properties of ℝ developed from the ordered field axioms ( Sections 8.1 , 8.2 , 8.3 , and possibly 8.4 ).
  从有序域公理发展出的 ℝ 的代数性质（第 8.1、8.2、8.3 节，以及可能的第 8.4 节）。

A course introducing ideas from advanced calculus could include these topics:

介绍高等微积分概念的课程可以包括以下主题：

• how to prove statements containing multiple quantifiers ( Sections 2.6 and 2.7 );
  如何证明包含多个量词的语句（第 2.6 节和第 2.7 节）；
• general unions and intersections ( Section 3.6 );
  一般联合体和交叉口（第 3.6 节）；
• properties of preimages of sets under functions ( Section 5.7 );
  函数作用下集合原像的性质（第 5.7 节）；
• countable and uncountable sets ( Sections 7.2 , 7.3 , and 7.4 );
  可数集和不可数集（第 7.2、7.3 和 7.4 节）；
• rigorous development of the real numbers (and related number systems) from the ordered field axioms ( Chapter 8 ).
  从有序域公理出发，严格发展实数（及相关数系）（第 8 章）。

A quarter-long (1500 minute) course focusing on basic proof methods might only cover Chapter 1 , Chapter 2 , and the early sections in Chapters 3 through 6 . A quarter course on set theory, aimed at students with some prior familiarity with logic and proofs, might cover all of Chapters 3 , 5 , 6 , and 7 .

一个为期一个季度（1500 分钟）的课程，重点讲解基本证明方法，可能只涵盖第 1 章、第 2 章以及第 3 章至第 6 章的前几节。一个为期一个季度的集合论课程，面向已经具备一些逻辑和证明知识的学生，可能涵盖第 3 章、第 5 章、第 6 章和第 7 章的全部内容。

Topics can also be studied in several different orders. Chapter 1 on logic must come first, and Chapter 2 on proof methods must come second. Thereafter, some flexibility is possible. Chapter 4 (on induction and basic number theory) can be covered before Chapter 3 (on sets) or omitted entirely. Chapter 6 (on equivalence relations) can be covered before the last five sections of Chapter 5 (on functions). Chapter 7 (on cardinality) requires material from Chapter 5 on bijections, but it does not rely heavily on Chapter 6 . Finally, the optional Chapter 8 (axiomatic development of the real numbers) could be covered anytime after Chapter 2 , with minor adjustments to avoid explicit mention of functions and relations. However, Chapter 8 is more challenging than it may appear at first glance. We are all so familiar with basic arithmetic and algebraic facts about real numbers that it requires considerable intellectual discipline to deduce these facts from the axioms without accidentally using a property not yet proved. Nevertheless, it is rewarding and instructive (albeit somewhat tedious) to work through this logical development of ℝ if time permits.

学习主题的顺序可以有多种选择。第一章（逻辑）必须先学，第二章（证明方法）必须后学。之后，学习顺序可以有一定的灵活性。第四章（归纳法和基础数论）可以在第三章（集合）之前学习，也可以完全省略。第六章（等价关系）可以在第五章（函数）的最后五节之前学习。第七章（基数）需要用到第五章关于双射的内容，但并不大量依赖第六章。最后，可选的第八章（实数的公理化推导）可以在第二章之后的任何时间学习，只需稍作调整，避免明确提及函数和关系即可。然而，第八章比乍看之下更具挑战性。我们都非常熟悉关于实数的基本算术和代数事实，因此，要从公理中推导出这些事实而不意外地使用尚未证明的性质，需要相当的思维能力。不过，如果时间允许的话，研究 ℝ 的这种逻辑发展过程是有益的，也是有启发性的（尽管有点枯燥）。

Book’s Approach to Key Topics

本书对关键主题的处理方法

This book adopts a methodical, detailed, and highly structured approach to teaching proof techniques and related mathematical topics. We start with basic logical building blocks and gradually assemble these ingredients to build more complex concepts. To give you a flavor of the teaching philosophy used here, the next few paragraphs describe my approach to explaining four key topics: proof-writing, functions, multiple quantifiers, and induction.

本书采用系统、详尽且结构严谨的方法教授证明技巧及相关数学主题。我们从基本的逻辑模块入手，逐步构建更复杂的概念。为了让您更好地了解本书的教学理念，接下来的几段将介绍我讲解四个关键主题的方法：证明写作、函数、多重量词和归纳法。

Additional Pedagogical Features

其他教学特色

(a) Section Summaries and Global Reviews. Every section ends with a concise recap of the key points just covered. Each major part of the text (logic and proofs; sets and integers; relations, functions, and cardinality) ends with a global review summarizing the material covered in that part. These reviews assemble many definitions, theorem statements, and proof techniques in one place, facilitating memorization and mastery of this vast amount of information.

（a）章节总结和全局回顾。每节课结尾都附有对刚刚讲解的关键点的简明总结。教材的每个主要部分（逻辑与证明；集合与整数；关系、函数与基数）结尾都有全局回顾，总结该部分的内容。这些回顾将大量的定义、定理陈述和证明技巧集中在一起，便于记忆和掌握这些海量信息。

(b) Avoiding Logical Jargon. This text avoids ponderous terminology from classical logic (such as conjunction, disjunction, modus ponens, modus tollens, modus tollendo ponens, hypothetical syllogism, constructive dilemma, universal instantiation, and existential instantiation). I use only those terms from logic that are essential for mathematical work (such as tautology, converse, contrapositive, and quantifier). My exposition replaces antiquated Latin phrases like “modus ponens” by more memorable English names such as “the Inference Rule for IF.” Similarly, I refer to the hypothesis P and the conclusion Q of the IF-statement P ⇒ Q , rather than calling P the antecedent and Q the consequent of this statement.

(b) 避免使用逻辑术语。本文避免使用古典逻辑中晦涩难懂的术语（例如合取、析取、肯定前件式、否定前件式、否定肯定前件式、假言三段论、构造性困境、全称实例化和存在实例化）。我仅使用对数学工作至关重要的逻辑术语（例如重言式、逆命题、逆否命题和量词）。我的阐述用更易于记忆的英文名称（例如“IF 推理规则”）取代了“肯定前件式”等古老的拉丁语短语。同样，对于 IF 语句 P ⇒ Q，我使用“假设”来指代假设 P 和结论 Q，而不是称 P 为该语句的前件，Q 为后件。

(c) Finding Useful Denials. This is one of the most crucial skills students learn in a proofs course. Every good textbook states the basic denial rules, but students do not always realize (and texts do not always emphasize) that the rules must be applied recursively to find a denial of a complex statement. I describe this recursive process explicitly in Section 1.5 (see especially the table on page 35). Section 1.6 reinforces this key skill with many solved sample problems and exercises.

(c) 寻找有用的否定。这是学生在证明课程中需要学习的最关键的技能之一。每本优秀的教科书都会阐述基本的否定规则，但学生并非总能意识到（教材也并非总能强调）这些规则必须递归地应用才能找到复杂命题的否定。我在第 1.5 节中详细描述了这个递归过程（尤其参见第 35 页的表格）。第 1.6 节通过大量的例题和练习巩固了这项关键技能。

(d) Annotated Proofs. Advanced mathematics texts often consist of a series of definitions, theorems, and proofs with little explanation given for how the author found the proofs. This text is filled with explicit annotations showing the reader how we are generating the lines of a proof, why we are proceeding in a certain way, and what the common pitfalls are. These annotations are clearly delineated from the official proof by enclosing them in square brackets. Many sample proofs are followed by commentary discussing important logical points revealed by the proof.

(d) 注释证明。高等数学教材通常由一系列定义、定理和证明组成，很少解释作者是如何得出这些证明的。本书则充满了清晰的注释，向读者展示我们如何生成证明的每一行，为什么我们采取某种方法，以及常见的陷阱是什么。这些注释用方括号括起来，与正式证明清晰区分开来。许多示例证明后都附有评注，讨论证明中揭示的重要逻辑要点。

(e) Disproofs Contrasted with Proofs by Contradiction. A very common student mistake is to confuse the disproof of a false statement P with a proof by contradiction of a true statement Q . This mistake occurs because of inattention to logical status words: the disproof of P begins with the goal of proving a denial of P , whereas a proof of Q by contradiction begins by assuming the denial of Q . We explicitly warn readers about this issue in Remark 2.60.

(e) 反证法与反证法的区别。学生常犯的一个错误是将对假命题 P 的反证法与对真命题 Q 的反证法混淆。这种错误源于对逻辑状态词的忽视：对 P 的反证法以证明 P 为否定命题为目标，而对 Q 的反证法则以假设 Q 为否定命题为目标。我们在注 2.60 中明确提醒读者注意这个问题。

(f) Set Definitions. New sets and set operations are often defined using set-builder notation. For example, the union of sets S and T is defined by writing S ∪ T = { x : x ∈ S or x ∈ T . This book presents these definitions in a format more closely matching how they arise in proofs, by explicitly stating what membership in the new set means. For instance, my definition of set union says that for all sets S and T and all objects x , the defined term x ∈ S ∪ T can be replaced by the definition text x ∈ S or x ∈ T at any point in a proof. This is exactly what the previous definition means, of course, but the extra layer of translation inherent in the set-builder notation causes trouble for many beginning students.

(f) 集合定义。新的集合和集合运算通常使用集合构造符号来定义。例如，集合 S 和 T 的并集定义为 S ∪ T = {x : x ∈ S 或 x ∈ T}。本书以一种更贴近证明中实际出现方式的格式来呈现这些定义，明确地说明了新集合的成员资格意味着什么。例如，我对集合并集的定义是：对于所有集合 S 和 T 以及所有对象 x，定义项 x∈S∪T 可以在证明中的任何位置替换为定义文本 x∈S 或 x∈T。这当然与之前的定义完全相同，但集合构造符号中固有的额外转换会给许多初学者带来困扰。

(g) Careful Organization of Optional Material. Advanced material and additional topics appear in clearly labeled optional sections. This organization provides maximum flexibility to instructors who want to supplement the material in the standard core, while signaling to readers what material may be safely skipped.

(g) 精心组织选修材料。进阶材料和补充主题列于清晰标注的选修章节中。这种组织方式既为希望补充标准核心教材内容的教师提供了最大的灵活性，又能引导读者了解哪些内容可以跳过。

Exercises, Errata, and Feedback

练习、勘误和反馈

The book contains more than 1000 exercises of varying scope and difficulty, which may be assigned as graded homework or used for self-study or review. I welcome your feedback about any aspect of this book, most particularly corrections of any errors that may be lurking in the following pages. Please send such communications to me by email at nloehr@vt.edu . I will post errata and other pertinent information on the book’s website.

本书包含1000多道练习题，难度和范围各不相同，既可作为作业布置并计分，也可用于自学或复习。我欢迎您就本书的任何方面提出反馈意见，尤其欢迎您指出书中可能存在的任何错误。请将此类反馈意见发送至我的邮箱：nloehr@vt.edu。我会在本书的网站上发布勘误表和其他相关信息。

Words of Thanks

致谢

Some pedagogical elements of this book were suggested by the exposition in A Transition to Advanced Mathematics by Smith, Eggen, and St. Andre. My debt to this excellent text will be evident to anyone familiar with it. My development as a mathematician and a writer has also been deeply influenced by the superb works of James Munkres, Joseph Rotman, J. Donald Monk, and the other authors listed in the Suggestions for Further Reading (see page 383). I thank all the editorial staff at CRC Press, especially Bob Ross and Jose Soto, and the anonymous reviewers whose comments greatly improved the quality of my original manuscript.

本书的部分教学理念借鉴了史密斯、埃根和圣安德烈合著的《高等数学的过渡》一书。任何熟悉此书的人都会明白我对这本优秀著作的感激之情。此外，詹姆斯·蒙克雷斯、约瑟夫·罗特曼、J·唐纳德·蒙克以及“延伸阅读建议”（见第383页）中列出的其他作者的杰出著作也对我的数学和写作发展产生了深远的影响。我衷心感谢CRC出版社的所有编辑人员，特别是鲍勃·罗斯和何塞·索托，以及匿名审稿人，他们的意见极大地提升了我原稿的质量。

I am grateful to many students, colleagues, friends, and family members who supported me during the preparation of this book. I especially thank my father Frank Loehr, my mother Linda Lopez, my stepfather Peter Lopez, Ken Zeger, Elizabeth Niese, Bill Floyd, Leslie Kay, and the students who took proofs classes from me over the years. Words cannot express how much I learned about teaching proofs from my students. Thank you all!

我衷心感谢在本书编写过程中给予我支持的众多学生、同事、朋友和家人。我尤其要感谢我的父亲弗兰克·洛尔、母亲琳达·洛佩兹、继父彼得·洛佩兹、肯·泽格、伊丽莎白·尼泽、比尔·弗洛伊德、莱斯利·凯，以及多年来跟随我学习证明课程的学生们。言语无法表达我从学生们身上学到了多少关于证明教学的知识。谢谢大家！

Propositions

命题

We begin with propositional logic , which studies how the truth of a complex statement is determined by the truth or falsehood of its parts.

我们从命题逻辑开始，它研究的是如何通过复杂陈述的真假来决定该陈述的真假。

Many things we say are not propositions, as seen in the next example.

我们所说的很多话并不是命题，如下例所示。

Solution. Statement (a) is a true proposition. Statement (b) is a false proposition. Commands, opinions, and questions do not have a truth value, so statements (c) through (e) are not propositions. Statement (f) is an example of a paradox : if you assume this statement is true, then the statement itself asserts that it is false. If you instead assume the statement is false, then the statement is also true. Since propositions are not allowed to be both true and false, statement (f) is not a proposition. Finally, statement (g) is a false proposition, for reasons described below.

解答：陈述 (a) 为真命题。陈述 (b) 为假命题。命令、意见和疑问句没有真值，因此陈述 (c) 至 (e) 不是命题。陈述 (f) 是一个悖论的例子：如果你假设该陈述为真，那么该陈述本身就断言它是假的。如果你反过来假设该陈述为假，那么该陈述也为真。由于命题不允许既为真又为假，因此陈述 (f) 不是命题。最后，陈述 (g) 为假命题，原因如下所述。

Propositional Forms

命题形式

Statement (g) in the last example is a complex proposition built up from two shorter propositions using logical connective words such as AND, NOT, OR. The two shorter propositions are “Paris is a city” and “2 + 2 is 4.” Let us abbreviate the proposition “Paris is a city” by the letter P , and let us abbreviate the proposition “2 + 2 is 4” by the letter Q . Then statement (g) has the form

上例中的命题 (g) 是一个复杂的命题，它由两个较短的命题构成，并使用了诸如 AND、NOT、OR 之类的逻辑连接词。这两个较短的命题分别是“巴黎是一座城市”和“2 + 2 等于 4”。我们用字母 P 来缩写命题“巴黎是一座城市”，用字母 Q 来缩写命题“2 + 2 等于 4”。那么，命题 (g) 的形式为：

We can create an even shorter expression to represent the logical form of statement (g) by introducing special symbols for the logical connectives. Propositional logic uses the six symbols shown in the following table, whose meaning is discussed in detail below.

我们可以通过引入逻辑连接词的特殊符号，创建一个更简洁的表达式来表示语句 (g) 的逻辑形式。命题逻辑使用下表所示的六个符号，其含义将在下文详细讨论。

Using these symbols, we can describe the logical form of statement (g) by the expression

利用这些符号，我们可以用表达式来描述语句 (g) 的逻辑形式。

Any expression like this, which is built up by combining propositional variables (capital letters) using logical symbols, is called a propositional form .

任何像这样的表达式，都是通过逻辑符号组合命题变量（大写字母）而构成的，称为命题形式。

Definitions of NOT and AND

“非”和“与”的定义

In logic and mathematics, language is used in a very precise way that does not always coincide with how words are used in everyday conversation. In particular, before going further, we need to define the exact meaning of the logical connective words NOT, AND, OR, IF, etc. To do this, we give truth tables that show how to combine the truth values of propositions to obtain the truth value of a new proposition built from these using a logical connective. Here and below, italic capital letters such as P , Q , R are variables that represent propositions. The letters T and F stand for true and false , respectively.

在逻辑和数学中，语言的使用非常精确，这与日常对话中词语的使用方式并不总是一致。尤其是在深入探讨之前，我们需要明确逻辑连接词“非”、“与”、“或”、“如果”等的确切含义。为此，我们提供了真值表，它展示了如何组合命题的真值，从而得到由这些命题通过逻辑连接词构建的新命题的真值。在下文中，斜体大写字母（例如 P、Q、R）代表命题。字母 T 和 F 分别代表真和假。

In our example above, where Q is the true proposition “2 + 2 is 4,” ~ Q is the false proposition “2 + 2 is not 4.” If R is the false proposition “9 is negative,” then ~ R is the true proposition “9 is not negative.”

在上面的例子中，如果 Q 是真命题“2 + 2 等于 4”，那么 ~Q 是假命题“2 + 2 不等于 4”。如果 R 是假命题“9 是负数”，那么 ~R 是真命题“9 不是负数”。

The remaining logical connectives combine two propositions to produce a new proposition. As seen in the next definition, we need a four-row truth table to list all possible truth values of the two propositions that we start with.

剩余的逻辑连接词将两个命题组合成一个新的命题。正如下一个定义所示，我们需要一个四行的真值表来列出这两个初始命题的所有可能真值。

In our running example, where P is the true proposition “Paris is a city” and Q is the true proposition “2 + 2 is 4,” note that P ∧ ( ∼ Q ) is false, because P is true and ~ Q is false. Similarly, ( ∼ P ) ∧ Q is false, because ~ P is false and Q is true. In this example, for any proposition R , we can deduce that ( ∼ P ) ∧ R must be false no matter what the truth value of R is, since ~ P is already false. On the other hand, P ∧ R is true for true propositions R , and false for false propositions R .

在我们的示例中，P 是真命题“巴黎是一座城市”，Q 是真命题“2 + 2 等于 4”。注意，P∧(∼Q) 为假，因为 P 为真且 ~Q 为假。类似地，(∼P)∧Q 也为假，因为 ~P 为假且 Q 为真。在这个例子中，对于任何命题 R，我们可以推断 (∼P)∧R 必然为假，无论 R 的真值是什么，因为 ~P 本身就是假的。另一方面，对于真命题 R，P∧R 为真；对于假命题 R，P∧R 为假。

Definitions of OR and XOR

OR 和 XOR 的定义

We now come to the mathematical definition of the word OR. In everyday English, the word OR can be used in two different ways. In the inclusive usage of this word, “ P or Q ” means that at least one of the propositions P , Q is true (possibly both). In the exclusive usage, “ P or Q ” means that exactly one of the propositions P , Q is true and the other one is false. Logic uses two different symbols for these two usages of the word OR: ∨ stands for inclusive-OR , and ⊕ stands for exclusive-OR (which is also abbreviated XOR). Remember this convention: in mathematics, the English word OR always means inclusive-OR , as defined by the truth table below. If you want to use XOR in mathematical English, you must use a longer phrase such as “ P or Q , but not both.”

现在我们来看“或”的数学定义。在日常英语中，“或”有两种不同的用法。在包含性用法中，“P 或 Q”表示命题 P 和 Q 中至少有一个为真（可能两者都为真）。在异或用法中，“P 或 Q”表示命题 P 和 Q 中恰好有一个为真，另一个为假。逻辑学使用两个不同的符号来表示“或”的这两种用法：∨ 表示包含性“或”，⊕ 表示异或（也称为 XOR）。请记住这个约定：在数学中，英语单词“或”始终表示包含性“或”，如下表所示。如果要在数学英语中使用“异或”，则必须使用更长的短语，例如“P 或 Q，但不能两者都为真”。

Remember this table by noting that P ∨ Q is false only when both inputs P , Q are false; in all other cases, P ∨ Q is true. To avoid confusing the symbols ∧ and ∨, it may help to notice that ∧ (the symbol for AND) resembles the diagonal strokes in the capital letter A.

记住这张表格的要点是：当且仅当输入 P 和 Q 都为假时，P∨Q 才为假；在所有其他情况下，P∨Q 都为真。为了避免混淆符号 ∧ 和 ∨，可以注意到 ∧（表示“与”的符号）的形状类似于大写字母 A 的斜线。

To complete our analysis of statement (g) above, recall in this example that ( P ∧ ( ∼ Q ) ) is false and ( ( ∼ P ) ∧ Q ) is false. So the overall statement is false. On the other hand, P ∨(~ Q ), (~ P )∨ Q , and P ∨ Q all stand for true propositions in this example.

为了完成对上述陈述 (g) 的分析，请记住，在本例中，(P∧(∼Q)) 为假，((∼P)∧Q) 也为假。因此，整个陈述为假。另一方面，在本例中，P∨(~Q)、(~P)∨Q 和 P∨Q 都代表真命题。

Truth Tables for Propositional Forms

命题形式的真值表

Given a complex propositional form built up from some variables using one or more logical connectives, we can determine the meaning of this form by making a truth table showing the truth value of the form for all possible combinations of truth values of the variables appearing in the form. We construct such a truth table step-by-step, making a column for each input variable and each smaller propositional form contained within the given form. We complete each column by using the defining truth tables (given above for ∼, ∧, ∨, ⊕ , and given in later sections for ⇒ and ⇔) to combine the truth values in one or two previously completed columns. We illustrate this process in the following examples.

给定一个由若干变量通过一个或多个逻辑连接词构建而成的复杂命题形式，我们可以通过构建真值表来确定其含义。真值表列出了该命题形式中所有变量真值组合的真值。我们逐步构建这样的真值表，为每个输入变量以及给定命题形式中包含的每个子命题形式创建一列。我们使用定义真值表（上文给出了∼、∧、∨、⊕的定义真值表，后续章节将给出⇒和⇔的定义真值表）来合并先前已完成的一列或两列中的真值，从而完成每一列。以下示例说明了这一过程。

In these examples, observe that the truth tables for ( P ∧ Q ) ∨ ( ∼ P ) and P ∧ ( Q ∨ ( ∼ P ) ) are not identical, since the outputs in rows 3 and 4 differ in the two tables. This shows that these two propositional forms are not logically interchangeable with one another in all situations. More briefly, we say that the two forms are not logically equivalent. On the other hand, if two propositional forms A and B have truth tables whose outputs agree in every row, we say that A and B are logically equivalent and write A ≡ B . (We study logical equivalence in detail in the next few sections.) Notice, for instance, that P ∧ ( Q ∨ ( ∼ P ) ) is logically equivalent to P ∧ Q , since column 5 in the previous example agrees with the truth table for P ∧ Q in all four rows. So we could write P ∧ ( Q ∨ ( ∼ P ) ) ≡ P ∧ Q , enabling us to replace the complicated propositional form on the left by the shorter form P ∧ Q on the right.

在这些例子中，请注意 (P∧Q)∨(∼P) 和 P∧(Q∨(∼P)) 的真值表并不相同，因为两个真值表第 3 行和第 4 行的输出不同。这表明这两个命题形式并非在所有情况下都能逻辑互换。简而言之，我们称这两个形式逻辑不等价。另一方面，如果两个命题形式 A 和 B 的真值表每一行的输出都相同，则称 A 和 B 逻辑等价，记作 A≡B。（我们将在接下来的几节中详细讨论逻辑等价性。）例如，请注意 P∧(Q∨(∼P)) 与 P∧Q 逻辑等价，因为前一个例子中的第 5 列与 P∧Q 的真值表在所有四行都相同。因此，我们可以写成 P∧(Q∨(∼P))≡P∧Q，从而可以用右边的较短形式 P∧Q 替换左边复杂的命题形式。

Formal Definition of Propositional Forms (Optional)

命题形式的正式定义（可选）

In the main text, we informally defined a propositional form to be any expression built up by combining propositional variables using logical symbols. To give a precise, rigorous definition of propositional forms, we need a recursive definition (definitions of this type are studied in detail later). Specifically, propositional forms are defined recursively via the following rules:

在正文中，我们非正式地将命题形式定义为任何由逻辑符号组合命题变量构成的表达式。为了给出命题形式的精确、严谨的定义，我们需要一个递归定义（此类定义将在后文详细讨论）。具体而言，命题形式通过以下规则进行递归定义：

(a) A single capital italic letter is a propositional form.

（a）单个大写斜体字母是命题形式。

(b) If A is any propositional form, then ( ∼ A ) is a propositional form.

（b）如果 A 是任意命题形式，则（∼A）也是命题形式。

(c) If A and B are any propositional forms, then ( A ∧ B ) is a propositional form.

（c）如果 A 和 B 是任意命题形式，则（A∧B）也是命题形式。

(d) If A and B are any propositional forms, then ( A ∨ B ) is a propositional form.

（d）如果 A 和 B 是任意命题形式，则（A∨B）也是命题形式。

(e) If A and B are any propositional forms, then ( A ⊕ B ) is a propositional form.

（e）如果 A 和 B 是任意命题形式，则（A⊕B）也是命题形式。

(f) If A and B are any propositional forms, then ( A ⇒ B ) is a propositional form.

（f）如果 A 和 B 是任意命题形式，则（A⇒B）也是命题形式。

(g) If A and B are any propositional forms, then ( A ⇔ B ) is a propositional form.

（g）如果 A 和 B 是任意命题形式，则（A⇔B）是命题形式。

(h) An expression is a propositional form only if it can be formed by applying rules (a) through (g) finitely many times.

（h）一个表达式是命题形式，当且仅当它可以由有限次应用规则（a）到（g）构成。

For example, rule (a) shows that P is a propositional form, as is Q . Then rule (b) shows that (~ P ) and (~ Q ) are propositional forms. By rule (c), ( P ∧ ( ∼ Q ) ) and ( ( ∼ P ) ∧ Q ) are propositional forms. By rule (d),

例如，规则 (a) 表明 P 是命题形式，Q 也是命题形式。那么规则 (b) 表明 (~P) 和 (~Q) 是命题形式。根据规则 (c)，(P∧(~Q)) 和 ((~P)∧Q) 也是命题形式。根据规则 (d)，

is a propositional form, which is essentially the form studied in (1.1) .

是命题形式，本质上是（1.1）中研究的形式。

However, to be absolutely precise, the expression in (1.1) is not a propositional form. This is because (1.1) is missing the outermost pair of parentheses, which are required to be present when using rules (b) through (g). In practice, we often drop required parentheses to create abbreviated versions of propositional forms that are easier to read. For instance, we seldom write the outermost pair of parentheses. Logical equivalences called associativity rules (discussed in the next section) allow us to drop internal parentheses in an expression like (( P ∨ Q )∨ R ) or ( P ∧ ( Q ∧ R ) ) . We can erase even more parentheses using the precedence conventions that ∼ has highest precedence, followed by ∧ , followed by ∨. For example, with these conventions, we could drop all parentheses from (1.2) and abbreviate this form as P ∧ ∼ Q ∨ ∼ P ∧ Q . However, as shown in Examples 1.8 and 1.9 , the placement of parentheses often affects the logical meaning of a propositional form (which is one reason why the official definition requires them). In this text, we often write parentheses that could be deleted by the precedence conventions, to reduce the chance of confusion.

然而，严格来说，(1.1) 式并非命题形式。这是因为 (1.1) 式缺少最外层的一对括号，而使用规则 (b) 至 (g) 时，这对括号是必需的。在实践中，我们经常省略必要的括号，以创建更易于阅读的命题形式的简写形式。例如，我们很少写出最外层的一对括号。逻辑等价关系，即结合律（将在下一节讨论），允许我们省略表达式（例如 ((P ∨ Q)∨R) 或 (P∧(Q∧R))）中的内部括号。我们可以使用优先级约定来省略更多的括号，其中 ∼ 的优先级最高，其次是 ∧，最后是 ∨。例如，按照这些约定，我们可以省略(1.2)式中的所有括号，并将该形式简写为P∧∼Q∨∼P∧Q。然而，如例1.8和1.9所示，括号的位置通常会影响命题形式的逻辑含义（这也是官方定义要求使用括号的原因之一）。在本文中，我们经常会使用一些根据优先级约定可以省略的括号，以减少混淆的可能性。

Section Summary

章节概要

1. Memorize the definitions of the logical connectives, as summarized in the following truth table.

1.记住逻辑连接词的定义，如下面的真值表所示。

Note that NOT flips the truth value of the input; AND outputs true exactly when both inputs are true; OR outputs false exactly when both inputs are false; and XOR outputs true exactly when the two inputs differ.

注意 NOT 会反转输入的真值；AND 会在两个输入都为真时输出真；OR 会在两个输入都为假时输出假；XOR 会在两个输入不同时输出真。

2. Remember that in mathematics, “ P or Q ” always means P ∨ Q (inclusive-OR). To translate P ⊕ Q (exclusive-OR) into English, you must use an explicit phrase such as “ P or Q , but not both.”

2. 请记住，在数学中，“P 或 Q”总是表示 P ∨ Q（包含或）。要将 P⊕Q（排除或）翻译成英语，您必须使用明确的短语，例如“P 或 Q，但不能同时是两者”。

3. Two propositional forms A and B are logically equivalent, denoted A ≡ B , when these forms have truth tables whose outputs agree in all rows of the truth table. If there is even a single row of disagreement, the forms are not logically equivalent. For instance, P ∨ Q ≢ P ⊕ Q .

3.当两个命题形式 A 和 B 的真值表在所有行中都一致时，这两个命题形式逻辑等价，记作 A≡B。如果哪怕只有一行不一致，这两个命题形式就不逻辑等价。例如，P∨Q≢P⊕Q。

Exercises

练习

1. Is each statement true, false, or not a proposition? Explain.

1. 下列陈述是真、假还是不是命题？请解释。

(a) 1 + 1 = 2 or London is a city. (b) Math is fun. (c) France is a country, and Berlin is an ocean. (d) 0 < 1 or 1 < 0. (e) 0 < 1 or 1 < 0, but not both. (f) Chopin was the greatest classical composer. (g) 2 is not even ¹ , or 2 is positive. (h) 15 is odd or positive, but not both.

(a) 1 + 1 = 2 或 伦敦是一座城市。(b) 数学很有趣。(c) 法国是一个国家，柏林是一片海洋。(d) 0 < 1 或 1 < 0。(e) 0 < 1 或 1 < 0，但两者不能同时成立。(f) 肖邦是最伟大的古典音乐作曲家。(g) 2 不是偶数，或者 2 是正数。(h) 15 是奇数或正数，但两者不能同时成立。

2. Is each statement true, false, or not a proposition? Explain.

2. 下列每个陈述是真、假还是不是命题？请解释。

(a) It is not the case that 2 is even or 2 is positive. (b) The following statement is a true proposition. (c) ∫ 0 1 x 2 d x = 1 / 3 and 2 ⁵ = 32. (d) When do fish sleep? (e) The following statement is a true proposition. (f) The previous statement is a false proposition. (g) I am tired.

(a) 2 不是偶数，也不是正数。(b) 以下命题为真。(c) ∫01x2dx=1/3 且 2 ⁵ = 32。(d) 鱼什么时候睡觉？(e) 以下命题为真。(f) 上一个命题为假。(g) 我累了。

3. Construct truth tables for the following propositional forms.

3. 为下列命题形式构造真值表。

(a) ( ∼ P ) ∧ Q (b) ( P ∧ Q ) ∨ ( ( ∼ P ) ∧ ( ∼ Q ) ) (c) ( P ∨ ( ∼ Q ) ) ⊕ ( ( ∼ Q ) ∨ P ) (d) ( P ∧ Q ) ∨ R (e) P ∧ ( Q ∨ R ) (f) P ∨ ( Q ⊕ R )

(a) (∼P)∧Q (b) (P∧Q)∨((∼P)∧(∼Q)) (c) (P∨(∼Q))⊕((∼Q)∨P) (d) (P∧Q)∨R (e) P∧(Q∨R) (f) P∨(Q⊕R)

4. (a) Is ~( P ∨ Q ) logically equivalent to (~ P )∨(~ Q )? Explain with a truth table. (b) Give English translations of the two propositional forms in (a).

4.(a) ~(P ∨ Q) 与 (~P)∨(~Q) 逻辑等价吗？用真值表解释。(b) 给出 (a) 中两个命题形式的英文翻译。

5. Assume P is a true proposition, Q is a false proposition, and R is an arbitrary proposition. Say as much as you can about the truth or falsehood of each proposition below.

5. 假设 P 为真命题，Q 为假命题，R 为任意命题。请尽可能详细地说明以下每个命题的真假。

(a) P ∧ ( ∼ Q ) (b) (~ P )∨ Q (c) P ⊕ Q (d) P ⊕ ( ∼ Q ) (e) R ∨ P (f) Q ∨ R (g) Q ⊕ R (h) R ∧ ( ∼ R ) (i) R ∨(~ R ) (j) R ⊕ R (k) R ⊕ ( ∼ R ) .

(a) P∧(∼Q) (b) (~P)∨Q (c) P⊕Q (d) P⊕(∼Q) (e) R∨P (f) Q∨R (g) Q⊕R (h) R∧(∼R) (i) R∨(~R) (j) R⊕R (k) R⊕(∼R).

6. (a) Make a truth table for the propositional form ( P ∧ ( ∼ Q ) ) ∨ ( ( ∼ P ) ∧ Q ) . Be sure to show the columns for all intermediate forms. (b) Find a short propositional form that is logically equivalent to the form in (a). (c) Use (b) to write an English sentence with the same logical meaning as statement (g) in Example 1.2 .

6.(a) 为命题形式 (P∧(∼Q))∨((∼P)∧Q) 构建真值表。务必显示所有中间形式的列。(b) 找到一个与 (a) 中的形式逻辑等价的简短命题形式。(c) 利用 (b) 的结果，写出一个与例 1.2 中的语句 (g) 逻辑含义相同的英文句子。

7. (a) Make a truth table for P ∧ ( ( ∼ Q ) ∨ P ) . (b) Make a truth table for ( P ∧ ( ∼ Q ) ) ∨ P . (c) Are the propositional forms in (a) and (b) logically equivalent? Why? (d) Find a short propositional form that is logically equivalent to the form in (a).

7.(a) 为 P∧((∼Q)∨P) 写出真值表。(b) 为 (P∧(∼Q))∨P 写出真值表。(c) (a) 和 (b) 中的命题形式逻辑等价吗？为什么？(d) 找到一个与 (a) 中的形式逻辑等价的简短命题形式。

8. Which propositional forms (if any) are logically equivalent? Justify your answer with truth tables.

8.哪些命题形式（如果有的话）在逻辑上等价？用真值表证明你的答案。

(a) P (b) ~ P (c) P ∨ P (d) P ∧ P (e) P ⊕ P (f) ( P ∧ Q ) ∨ P .

（a）P （b）~P （c）P ∨ P （d）P∧P （e）P⊕P （f）(P∧Q)∨P。

9. Which propositional forms (if any) are logically equivalent? Explain.

9.哪些命题形式（如果有的话）在逻辑上等价？请解释。

(a) P ∧ Q (b) Q ∧ P (c) ( P ∧ Q ) ∧ P (d) ∼ ( P ⊕ Q ) .

（a）P∧Q （b）Q∧P （c）(P∧Q)∧P （d）∼(P⊕Q)。

10. Which propositional forms (if any) are logically equivalent? Explain.

10.哪些命题形式（如果有的话）在逻辑上是等价的？请解释。

(a) ∼ ( P ∧ Q ) (b) ( ∼ P ) ∧ ( ∼ Q ) (c) ( ( ∼ P ) ∧ Q ) ∨ ( P ∧ ( ∼ Q ) ) (d) P ⊕ ( ∼ Q ) (e) P ∨(~ Q ) (f) ( P ∨ ( ∼ Q ) ) ∧ ( ( ∼ P ) ∨ Q ) .

(a) ∼(P∧Q) (b) (∼P)∧(∼Q) (c) ((∼P)∧Q)∨(P∧(∼Q)) (d) P⊕(∼Q) (e) P∨(~Q) (f) (P∨(∼Q))∧((∼P)∨Q).

11. Which propositional forms (if any) are logically equivalent? Explain.

11.哪些命题形式（如果有的话）在逻辑上是等价的？请解释。

(a) P ∨( Q ∨ R ) (b) P ⊕ ( Q ∨ R ) (c) P ∨ ( Q ⊕ R ) (d) P ⊕ ( Q ⊕ R ) (e) ( P ∨ Q )∨ R (f) ( P ⊕ Q ) ∨ R (g) ( P ∨ Q ) ⊕ R (h) ( P ⊕ Q ) ⊕ R .

（a）P∨(Q∨R) （b）P⊕(Q∨R) （c）P∨(Q⊕R) （d）P⊕(Q⊕R) （e）(P∨Q)∨R （f）(P⊕Q)∨R （g）(P∨Q)⊕R （h）(P⊕Q)⊕R。

12. Let x ₀ be a fixed integer. Let P be the proposition “ x ₀ < 8,” let Q be “0 < x ₀ ,” and let R be “ x ₀ = 0.” Encode each statement as a propositional form involving P , Q , and R .

12.设 x ₀ 为一个固定的整数。设 P 为命题“x ₀ < 8”，Q 为“0 < x ₀ ”，R 为“x ₀ = 0”。将每个语句编码为包含 P、Q 和 R 的命题形式。

(a) x ₀ is strictly positive. (b) x ₀ ≥ 8. (c) x ₀ is less than zero. (d) x ₀ is nonnegative. (e) 0 < x ₀ < 8. (f) 0 ≤ x ₀ < 8. (g) | x ₀ − 4| ≥ 4.

(a) x ₀ 严格为正。(b) x ₀ ≥ 8。(c) x ₀ 小于零。(d) x ₀ 非负。(e) 0 < x ₀ < 8。(f) 0 ≤ x ₀ < 8。(g) |x ₀ − 4| ≥ 4。

13. Let P be the statement “1 + 1 = 2,” let Q be “0 = 1,” and let R be “71 is prime.” Convert each propositional form into an English sentence without parentheses . Be sure that the sentence has the precise logical structure encoded by the form.

13.设 P 为命题“1 + 1 = 2”，Q 为命题“0 = 1”，R 为命题“71 是素数”。将每个命题形式转换为不含括号的英文句子。确保句子具有与命题形式精确一致的逻辑结构。

(a) ( P ∧ Q ) ∨ R (b) P ∧ ( Q ∨ R ) (c) ∼ ( P ∧ Q ) (d) ( ∼ P ) ∧ Q (e) ( P ∧ Q ) ∧ R (f) P ∧ ( Q ∧ R ) (g) ( ( ∼ P ) ∧ ( ∼ Q ) ) ⊕ ( ∼ R )

(a) (P∧Q)∨R (b) P∧(Q∨R) (c) ∼(P∧Q) (d) (∼P)∧Q (e) (P∧Q)∧R (f) P∧(Q∧R) (g) ((∼P)∧(∼Q))⊕(∼R)

14. Explain why each statement is not a proposition.

14.解释为什么每个陈述都不是命题。

(a) The last train leaves in five minutes. (b) We should raise the minimum wage. (c) Will you marry me? (d) My father’s name is Frank. (e) She is smarter than he is. (f) Do your homework. (g) It is cold here. (h) This statement is true.

(a) 末班车还有五分钟就开了。(b) 我们应该提高最低工资。(c) 你愿意嫁给我吗？(d) 我父亲名叫弗兰克。(e) 她比他聪明。(f) 做你的作业。(g) 这里很冷。(h) 这句话是正确的。

15. Find propositional forms using only the connectives ∨, ∧ , and ∼ that have the truth tables shown below. Try to use as few connectives as possible.

15.仅使用连接词∨、∧和∼，找出满足以下真值表的命题形式。尽量使用最少的连接词。

16. (a) Find a simple verbal description characterizing when ( ( A ⊕ B ) ⊕ ( C ⊕ D ) ) ⊕ E is true. (b) Does your answer to (a) change if we rearrange parentheses in the expression? What if we reorder A , B , C , D , and E ?

16.(a) 用简单的文字描述 ((A⊕B)⊕(C⊕D))⊕E 成立的条件。(b) 如果重新排列表达式中的括号，(a) 的答案会改变吗？如果重新排列 A、B、C、D 和 E 的顺序呢？

17. Find a propositional form involving variables P , Q , R that is true precisely when exactly one of P , Q , R is true. Try to use as few logical connectives as possible.

17. 找到一个包含变量 P、Q、R 的命题形式，使得该命题为真当且仅当 P、Q、R 中恰好有一个为真。尽量少用逻辑连接词。

18. Find a propositional form involving variables P , Q , R that is true when at least two of the inputs are true, and false otherwise. Try to use as few logical connectives as possible.

18. 找出包含变量 P、Q、R 的命题形式，当至少两个输入为真时该命题为真，否则为假。尽量少用逻辑连接词。

19. (a) How many truth tables are possible for propositional forms containing two variables P and Q ? (b) For each possible truth table in (a), find a short propositional form having that truth table.

19.(a) 包含两个变量 P 和 Q 的命题形式有多少种可能的真值表？(b) 对于 (a) 中的每一种可能的真值表，找到一个具有该真值表的简短命题形式。

Logical Equivalence

逻辑等价性

We first recall the definition of logically equivalent propositional forms from the last section.

我们首先回顾上一节中逻辑等价命题形式的定义。

Our first theorem lists some logical equivalences that can often be used to replace complicated propositional forms by shorter ones.

我们的第一个定理列出了一些逻辑等价关系，这些关系通常可以用来用更短的命题形式来代替复杂的命题形式。

All parts of this theorem are proved by constructing truth tables for the propositional forms on each side of each equivalence, and verifying that the truth tables agree in every row. We illustrate the technique for a few parts of the theorem, asking you to prove the other parts in the exercises.

本定理的所有部分均可通过为每个等价式两侧的命题形式构造真值表，并验证真值表每一行都一致来证明。我们将用此方法证明定理的几个部分，其余部分则需在练习中证明。

Columns 4 and 7 agree in every row, so the logical equivalence is proved. This equivalence and its companion ∼ ( P ∧ Q ) ≡ ( ∼ P ) ∨ ( ∼ Q ) are called de Morgan’s laws . In words, the law we just proved says that the negation of an OR-statement “ P or Q ” is equivalent to the statement “(not P ) and (not Q ),” whereas the dual law tells us that “not ( P and Q )” is logically equivalent to “(not P ) or (not Q ).” For a specific example, the statement “it is false that 10 is prime or 10 is odd” may be simplified to the statement “10 is not prime and 10 is not odd” without changing the truth value (both statements are true). Similarly, the statement that “John has brown hair AND blue eyes” is false precisely when John’s hair is not brown OR John’s eyes are not blue. In §1.5 , we will say a lot more about simplifying statements that begin with NOT.

第 4 列和第 7 列每一行都一致，因此逻辑等价性得证。这个等价性及其对应的等价性 ∼(P∧Q)≡(∼P)∨(∼Q) 被称为德摩根定律。用文字表述，我们刚刚证明的定律指出，OR 语句“P 或 Q”的否定等价于语句“(非 P) 且 (非 Q)”，而对应的定律则指出，“非 (P 且 Q)”逻辑等价于“(非 P) 或 (非 Q)”。举个具体的例子，“10 是质数或 10 是奇数为假”这个语句可以简化为“10 不是质数且 10 不是奇数”，而真值不变（两个语句都为真）。类似地，“约翰有棕色头发且蓝色眼睛”这个语句为假，当且仅当约翰的头发不是棕色或约翰的眼睛不是蓝色。在 §1.5 中，我们将更详细地讨论如何简化以 NOT 开头的语句。

The quickest way to fill in this truth table is to look for disagreements between the inputs of each XOR (being sure to refer to the correct columns), writing Ts in those rows, and writing Fs in all other rows. Columns 5 and 7 agree in all eight rows, so the associative law for ⊕ is proved. The other associative laws and distributive laws are proved by similar eight-row truth tables.

填写此真值表的最快方法是找出每个异或运算的输入之间的不一致之处（务必参考正确的列），在这些行中填写真（T），在所有其他行中填写假（F）。第 5 列和第 7 列在所有八行中都一致，因此 ⊕ 的结合律得证。其他结合律和分配律可以通过类似的八行真值表来证明。

What IF Means

“如果”的含义

We are now ready to define the precise logical meaning of the word IF. Be warned that the usage of IF in everyday conversational English often does not match the definition we are about to give. Nevertheless, this definition is universally used in logic, mathematics, and all technical communication. When discussing the statement P ⇒ Q , which is read “if P then Q ,” we call P the hypothesis and Q the conclusion of the IF-statement.

现在我们准备定义“如果”一词的精确逻辑含义。需要注意的是，日常英语口语中“如果”的用法通常与我们即将给出的定义不符。然而，这个定义在逻辑学、数学和所有技术交流中都被普遍使用。在讨论命题 P ⇒ Q（读作“如果 P 则 Q”）时，我们称 P 为假设，Q 为结论。

Remember this table by noting that P ⇒ Q is false only when the hypothesis P is true and the conclusion Q is false; in all other situations , the IF-statement is true. In particular, when P is false, the IF-statement P ⇒ Q is automatically true, whether Q is true or false; this fact often confuses beginners.

记住这张表格，注意只有当假设 P 为真且结论 Q 为假时，P ⇒ Q 才为假；在所有其他情况下，该 IF 语句都为真。尤其需要注意的是，当 P 为假时，无论 Q 为真还是假，IF 语句 P ⇒ Q 都自动为真；这一点常常会让初学者感到困惑。

It is fair to ask why IF is defined in such an apparently unnatural way. Most people agree that “if true then true” should be considered true, whereas “if true then false” should be considered false. Why, though, is “if false then anything” defined to be true? One possible answer draws an analogy between IF-statements, as they are used in logic, and IF-statements appearing in legal contracts or judicial proceedings. Suppose a painting company issues a contract to a homeowner containing the statement: “if you pay us $1000 by May 1, then we will paint your house by June 1.” Under what conditions would we say that the company has violated this contract? For example, suppose the company does not paint the house because it was not paid on time. Both clauses of the IF-statement are false, yet no one would say that the company violated the contract in this situation. Similarly, supposing that the money is paid on May 3 and the house is painted on time, the company has not violated the contract even though the first part of the IF-statement is false.

我们有理由质疑，为什么“如果”的定义如此不合常理。大多数人认同“如果为真，则为真”应被视为真，“如果为真，则为假”应被视为假。然而，为什么“如果为假，则任何事”被定义为真呢？一种可能的解释是，将逻辑中使用的“如果”语句与法律合同或司法程序中出现的“如果”语句进行类比。假设一家油漆公司与房主签订了一份合同，其中包含这样一条条款：“如果您在5月1日前支付我们1000美元，我们将在6月1日前粉刷您的房屋。”在什么情况下我们会认为该公司违反了合同？例如，假设该公司因为没有按时收到款项而没有粉刷房屋。在这种情况下，“如果”语句的两个条件都是假的，但没有人会认为该公司违反了合同。同样地，假设款项在 5 月 3 日支付，房屋也按时粉刷完毕，即使 IF 语句的第一部分是错误的，该公司也没有违反合同。

We can give another, more mathematical motivation for the definition of IF by considering the following statement: “for all real numbers x , if x > 2 then x ² > 4.” (This statement uses variables and quantifiers, which are discussed later.) Most people would judge this statement to be true, on intuitive grounds, and this judgment is correct. But once you agree this statement should be true, you are forced to agree that it should be true after replacing each x in the statement by any specific real number. In particular, we see that each of these statements must be true:

我们可以通过考虑以下语句，为“如果”的定义提供另一种更具数学性的解释：“对于所有实数 x，如果 x > 2，则 x > 4。”（该语句使用了变量和量词，我们将在后面讨论。）大多数人会凭直觉判断该语句为真，而这种判断是正确的。但是，一旦你认同该语句为真，你就必然会认同，将语句中的每个 x 替换为任何特定的实数后，该语句仍然为真。具体来说，我们可以看到以下每个语句都必然为真：

Thus the whole truth table for IF is forced upon us, granting that row 2 of the truth table ought to be false.

因此，IF 的整个真值表被强加给我们，前提是真值表的第 2 行应该是假的。

In mathematics, a statement “if P then Q ” is not making any claims about the truth of the conclusion Q in the event that the hypothesis P does not hold; so in this event, we should not declare the IF-statement to be false. But since propositions must have some truth value, we are forced to call the IF-statement true in such situations.

在数学中，“如果 P 则 Q”这样的陈述并没有对假设 P 不成立时结论 Q 的真假做出任何断言；因此，在这种情况下，我们不应该断言这个“如果”陈述为假。但由于命题必须具有真值，我们不得不在这种情况下称这个“如果”陈述为真。

Converse and Contrapositive

逆命题和逆否命题

Given an IF-statement P ⇒ Q , we can form two related IF-statements called the converse and contrapositive of the original statement.

给定一个 IF 语句 P ⇒ Q，我们可以形成两个相关的 IF 语句，分别称为原语句的逆命题和逆否命题。

In both examples, the contrapositive had the same truth value as the original statement, but this was not always the case for the converse. The next theorem explains what happens in general.

在这两个例子中，逆否命题的真值与原命题相同，但逆命题并非总是如此。下一个定理解释了一般情况下会发生什么。

Part (a) says that a general IF-statement is not logically equivalent to its converse. Part (b) says that a general IF-statement is logically equivalent to its contrapositive. Part (c) says that IF-statements are essentially special kinds of OR-statements in which the first input to the OR has been negated. We can use (c) to convert IF-statements to OR-statements and vice versa. Part (d) shows that the negation of an IF-statement is logically equivalent to an AND-statement. Parts (b), (c), and (d) hold for any propositional forms P and Q , not just individual letters. For instance, ( A ∨ B ) ⇒ ( C ⊕ D ) ≡ ( ∼ ( A ∨ B ) ) ∨ ( C ⊕ D ) follows by replacing P by A ∨ B and replacing Q by C ⊕ D in part (c). Memorize all parts of this theorem , as they will be used constantly throughout our study of logic and proofs.

(a) 部分指出，一般的 IF 语句与其逆命题逻辑不等价。(b) 部分指出，一般的 IF 语句与其逆否命题逻辑等价。(c) 部分指出，IF 语句本质上是特殊的 OR 语句，其中 OR 语句的第一个输入被取反。我们可以利用 (c) 部分将 IF 语句转换为 OR 语句，反之亦然。(d) 部分表明，IF 语句的否定逻辑等价于 AND 语句。(b)、(c) 和 (d) 部分适用于任何命题形式 P 和 Q，而不仅仅是单个字母。例如，(A∨B)⇒(C⊕D)≡(∼(A∨B))∨(C⊕D) 可以通过将 (c) 部分中的 P 替换为 A ∨ B，将 Q 替换为 C⊕D 得到。记住这个定理的所有部分，因为它们将在我们学习逻辑和证明的过程中不断用到。

To prove the theorem, consider the following truth table:

为了证明该定理，请考虑以下真值表：

Column 3 does not match column 4 in rows 2 and 3, proving (a). Column 3 matches column 7 in all rows, proving (b). Column 3 also matches column 8 in all rows, proving (c). We can prove (d) by adding a few more columns to this truth table. Alternatively, (d) follows from (c) and the Negation Laws, since

第 2 行和第 3 行的第 3 列与第 4 列不匹配，证明 (a)。第 3 列与所有行的第 7 列匹配，证明 (b)。第 3 列也与所有行的第 8 列匹配，证明 (c)。我们可以通过向真值表中添加几列来证明 (d)。或者，(d) 可由 (c) 和否定定律得出，因为

Five Remarks on Logical Equivalence (Optional)

关于逻辑等价性的五点说明（可选）

(1) The Theorem on Logical Equivalence shows that many of the laws of logic have an algebraic character analogous to algebraic laws for arithmetical operations on real numbers. To make this analogy more explicit, we introduce the convention of representing true (T) by 1 and false (F) by 0. The symbols 0 and 1 are called bits . In this notation, the defining truth tables for the six logical operators (including IFF, discussed in the next section) look like this:

（1）逻辑等价定理表明，许多逻辑定律具有类似于实数运算代数定律的代数特性。为了更明确地表达这种类比，我们引入用 1 表示真 (T)、用 0 表示假 (F) 的约定。符号 0 和 1 被称为比特。在这种表示法下，六个逻辑运算符（包括下一节讨论的 IFF）的定义真值表如下所示：

If we think of P and Q as bits (the actual integers 0 and 1, rather than propositions), we see that ~ P = 1 − P ; P ∧ Q = P ⋅ Q = min ( P , Q ) , the product or minimum of P and Q ; P ∨ Q = max ( P , Q ), the maximum of P and Q ; and P ⊕ Q is the mod-2 sum of P and Q . (We discuss modular addition in detail later.) We can also think of ⊕ , ⇒, and ⇔ as relations comparing their two inputs. In this interpretation, P ⊕ Q is true precisely when P ≠ Q , so ⊕ models non-equality of bits; P ⇔ Q is true precisely when P = Q , so ⇔ models equality of bits; and P ⇒ Q is true precisely when P ≤ Q , so ⇒ models ordering of bits. Now the various identities in the Theorem on Logical Equivalences translate into identities for these algebraic operations on bits. For instance, supposing we already know that x ( yz ) = ( xy ) z for all integers x , y , z , we can deduce the associativity law P ∧ ( Q ∧ R ) ≡ ( P ∧ Q ) ∧ R for propositional forms.

如果我们把 P 和 Q 看作比特（实际的整数 0 和 1，而不是命题），那么 ~P = 1 − P；P∧Q=P⋅Q=min(P,Q)，即 P 和 Q 的乘积或最小值；P ∨ Q = max(P, Q)，即 P 和 Q 的最大值；P⊕Q 是 P 和 Q 的模 2 和。（我们稍后会详细讨论模加法。）我们还可以将 ⊕、⇒ 和 ⇔ 看作是比较两个输入的关系。在这种解释下，P⊕Q 为真当且仅当 P ≠ Q，因此 ⊕ 表示比特不相等；P ⇔ Q 为真当且仅当 P = Q，因此 ⇔ 表示比特相等；P ⇒ Q 为真当且仅当 P ≤ Q，因此 ⇒ 表示比特的顺序。现在，逻辑等价定理中的各种恒等式可以转化为这些位代数运算的恒等式。例如，假设我们已经知道对于所有整数 x、y、z，都有 x(yz) = (xy)z，那么我们可以推导出命题形式的结合律 P∧(Q∧R)≡(P∧Q)∧R。

(2) Logical equivalence of propositional forms (denoted ≡) is similar to, but not the same as, equality of forms (denoted =). Thinking of propositional forms A and B as strings of symbols, A = B means that A has exactly the same symbols as B , in the same order. For example, P ∨ Q is not equal to Q ∨ P since the first symbols do not match. Yet, as we know, P ∨ Q ≡ Q ∨ P since the two truth tables agree. For most purposes of logic, two logically equivalent forms are interchangeable with each other (since their truth values must agree), even though such forms are often not equal as strings.

(2) 命题形式的逻辑等价性（记为≡）类似于形式的相等性（记为=），但并不相同。将命题形式A和B视为符号串，A=B表示A和B包含完全相同的符号，且顺序也相同。例如，P∨Q不等于Q∨P，因为前几个符号不匹配。然而，我们知道P∨Q≡Q∨P，因为这两个命题的真值表一致。在大多数逻辑应用中，两个逻辑等价的形式可以互换使用（因为它们的真值必须一致），即使它们作为字符串时通常并不相等。

(3) Although logical equivalence of propositional forms (denoted ≡) is not the same concept as logical equality (denoted =), these two concepts share many common properties. For example, given any objects x , y , z whatsoever, the following facts are true about equality:

（3）虽然命题形式的逻辑等价（记为≡）与逻辑相等（记为=）并非同一概念，但二者有很多共同的性质。例如，对于任意对象x、y、z，关于相等性，以下事实成立：

These facts are called reflexivity , symmetry , and transitivity of equality. Three analogous facts also hold for logical equivalence: given any propositional forms A , B , C ,

这些事实被称为等式的自反性、对称性和传递性。逻辑等价性也具有三个类似的性质：给定任意命题形式 A、B、C，

These facts follow from the corresponding facts for equality, applied to the rows of the truth tables. For instance, if the output in every row of A ’s truth table equals the corresponding output of B ’s truth table, then the output in every row of B ’s truth table equals the corresponding output of A ’s truth table, which is why the second fact is true. The text implicitly uses the reflexivity, symmetry, and transitivity of logical equivalence in many places. For instance, the derivation (1.3) has the form A ≡ B ≡ C ≡ D , which is really an abbreviation for “ A ≡ B and B ≡ C and C ≡ D .” Using transitivity once, we see that A ≡ C . Using transitivity again, we see that A ≡ D , which is the required conclusion. Similarly, symmetry of ≡ is needed whenever we want to use a known logical equivalence in reverse, e.g., to replace ( P ∧ Q ) ∨ ( P ∧ R ) by P ∧ ( Q ∨ R ) by invoking the Distributive Law. We will have much more to say about the properties of reflexivity, symmetry, and transitivity in Chapter 6 , when we study equivalence relations.

这些事实源于等式的相应事实，并应用于真值表的每一行。例如，如果A真值表每一行的输出都等于B真值表的对应输出，那么B真值表每一行的输出也都等于A真值表的对应输出，这就是第二个事实为真的原因。文中多处隐含地运用了逻辑等价的自反性、对称性和传递性。例如，推导式(1.3)的形式为A≡B≡C≡D，实际上是“A≡B且B≡C且C≡D”的缩写。运用一次传递性，我们得出A≡C。再次运用传递性，我们得出A≡D，这正是所需的结论。类似地，当我们想要反向使用已知的逻辑等价关系时，例如，通过运用分配律将 (P∧Q)∨(P∧R) 替换为 P∧(Q∨R)，就需要用到 ≡ 的对称性。关于自反性、对称性和传递性的性质，我们将在第六章学习等价关系时进行更详细的讨论。

(4) The logical equivalences in this section’s theorems apply to all propositional forms P , Q , R , which means that we can replace each letter P , Q , R (wherever it appears in an identity) by a longer propositional form. For instance, replacing P by A ⇒ B and Q by B ⊕ C in the second negation law, we see that ∼ ( ( A ⇒ B ) ∧ ( B ⊕ C ) ) ≡ ( ∼ ( A ⇒ B ) ) ∨ ( ∼ ( B ⊕ C ) ) . In contrast, consider the non-logical equivalence asserted in part (a) of the Theorem on IF. In that theorem, P and Q are distinct propositional variables (as opposed to general propositional forms), and we have ( P ⇒ Q ) ≢ ( Q ⇒ P ) as shown in the proof. But for some choices of the form P and the form Q , the logical equivalence will hold; for instance, suppose P and Q are both R . It can be checked that when P and Q are logically equivalent forms, ( P ⇒ Q ) ≡ ( Q ⇒ P ), because in this case we must always be in row 1 or row 4 of the truth table shown in the proof. (In fact, using terminology from the next section, P ⇒ Q and Q ⇒ P are both tautologies in this situation.) For example, (( A ∨ B ) ⇒ ( B ∨ A )) is logically equivalent to (( B ∨ A ) ⇒ ( A ∨ B )). On the other hand, when P and Q are not logically equivalent, there must exist some assignment of truth values to the propositional variables appearing in P and Q that cause P and Q themselves to have opposite truth values. In this row of the truth table, P ⇒ Q and Q ⇒ P disagree, so that these forms are not logically equivalent. For instance, ( ( A ∨ B ) ⇒ ( A ⊕ B ) ) and ( ( A ⊕ B ) ⇒ ( A ∨ B ) ) are not logically equivalent, as we see by considering the row of the truth table where A and B are both true.

(4) 本节定理中的逻辑等价性适用于所有命题形式 P、Q、R，这意味着我们可以将每个字母 P、Q、R（无论它出现在等价关系中的哪个位置）替换为更长的命题形式。例如，在第二否定法则中，将 P 替换为 A ⇒ B，将 Q 替换为 B⊕C，我们可以看到 ∼((A⇒B)∧(B⊕C))≡(∼(A⇒B))∨(∼(B⊕C))。相比之下，考虑关于 IF 的定理 (a) 部分中断言的非逻辑等价性。在该定理中，P 和 Q 是不同的命题变量（而不是一般的命题形式），并且我们有 (P⇒Q)≢(Q⇒P)，如证明所示。但是对于某些形式的 P 和形式 Q 的选择，逻辑等价性仍然成立；例如，假设 P 和 Q 都是 R。可以验证，当 P 和 Q 是逻辑等价形式时，(P ⇒ Q) ≡ (Q ⇒ P)，因为在这种情况下，我们必然总是位于证明中所示真值表的第 1 行或第 4 行。（事实上，使用下一节的术语，在这种情况下，P ⇒ Q 和 Q ⇒ P 都是重言式。）例如，((A ∨ B) ⇒ (B ∨ A)) 逻辑等价于 ((B ∨ A) ⇒ (A ∨ B))。另一方面，当 P 和 Q 不逻辑等价时，必然存在某种赋予 P 和 Q 中出现的命题变量的真值，使得 P 和 Q 本身具有相反的真值。在真值表的这一行中，P ⇒ Q 和 Q ⇒ P 的真值不一致，因此这些形式不逻辑等价。例如，((A∨B)⇒(A⊕B)) 和 ((A⊕B)⇒(A∨B)) 在逻辑上并不等价，我们可以通过考虑真值表中 A 和 B 都为真的那一行来看出这一点。

(5) In algebra, if we know two variables represent the same number, we can replace one variable by the other in longer expressions. We can express this fact symbolically by substitution rules such as the following: for all numbers x , y , z , if y = z then x + y = x + z and xy = xz . There are analogous substitution rules for logically equivalent propositional forms. For instance, given any propositional forms A , B , and C , if B ≡ C , then ( A ∨ B ) ≡ ( A ∨ C ) , ( A ∧ B ) ≡ ( A ∧ C ) , ( A ⇒ B ) ≡ ( A ⇒ C ) , ( B ⇒ A ) ≡ ( C ⇒ A ) , and so on. We freely use these substitution rules without justification in the main text, but it is possible to prove each rule by comparing truth tables. As an example, assume B ≡ C , and consider a fixed row in the truth tables for A ⇒ B and A ⇒ C . Suppose that, for the values of the input propositional variables appearing in this row, A is true and B is false. On one hand, A ⇒ B must be false in this row. On the other hand, since B and C were assumed to be logically equivalent, C is false in this row, so A ⇒ C is also false in this row. Thus, A ⇒ B and A ⇒ C have the same truth value (namely, false) in this row. Considering the other possible cases, we see that A ⇒ B and A ⇒ C have the same truth value in every row of the truth table, so they are logically equivalent. We can summarize the cases in a meta-truth table that looks like this:

(5) 在代数中，如果我们知道两个变量代表同一个数，就可以在较长的表达式中用一个变量替换另一个变量。我们可以用替换规则来符号化地表达这个事实，例如：对于任意数 x、y、z，如果 y = z，则 x + y = x + z 且 xy = xz。对于逻辑等价的命题形式，也有类似的替换规则。例如，给定任意命题形式 A、B 和 C，如果 B≡C，则 (A∨B)≡(A∨C)，(A∧B)≡(A∧C)，(A⇒B)≡(A⇒C)，(B⇒A)≡(C⇒A)，等等。我们在正文中随意使用这些替换规则而没有给出理由，但可以通过比较真值表来证明每条规则。例如，假设 B≡C，并考虑 A⇒B 和 A⇒C 真值表中的固定行。假设对于本行中出现的输入命题变量的值，A 为真，B 为假。一方面，A⇒B 在本行中必然为假。另一方面，由于假设 B 和 C 逻辑等价，C 在本行中为假，因此 A⇒C 在本行中也为假。所以，A⇒B 和 A⇒C 在本行中具有相同的真值（即假）。考虑其他可能的情况，我们发现 A⇒B 和 A⇒C 在真值表的每一行中都具有相同的真值，因此它们逻辑等价。我们可以将这些情况总结在一个元真值表中，如下所示：

We call this a meta-truth table because the underlying propositional variables appearing in A , B , and C are not explicitly listed. (For example, these forms might involve five propositional variables P , Q , R , S , and T , so that the actual truth table would have 32 rows.) However, to prove the logical equivalence of A ⇒ B and A ⇒ C , we only need to know the truth values of the propositional forms A , B , and C . Row 2 of the table is an abbreviation for the discussion preceding the table, and the other rows cover the remaining cases. The key point is that the table has four rows, not eight, because we have assumed that B and C are logically equivalent forms, hence always have the same truth value. You can construct similar meta-truth tables to prove the other substitution rules.

我们称之为元真值表，因为A、B和C中出现的底层命题变量并未明确列出。（例如，这些形式可能涉及五个命题变量P、Q、R、S和T，因此实际的真值表将有32行。）然而，为了证明A⇒B和A⇒C的逻辑等价性，我们只需要知道命题形式A、B和C的真值即可。表的第2行是对前面讨论的简要概括，其余行涵盖了剩余的情况。关键在于该表只有四行而不是八行，因为我们假设B和C是逻辑等价的形式，因此它们的真值始终相同。您可以构建类似的元真值表来证明其他替换规则。

Section Summary

章节概要

1. The logical operators satisfy the commutative, associative, distributive, idempotent, and absorption laws listed in the Theorem on Logical Equivalence. They also obey these negation rules:

1. 逻辑运算符满足逻辑等价定理中列出的交换律、结合律、分配律、幂等律和吸收律。它们也遵循以下否定规则：

We check all these logical equivalences by verifying that the truth tables for each side agree in every row.

我们通过验证每一方的真值表在每一行都一致来检验所有这些逻辑等价性。

2. P ⇒ Q is false when P is true and Q is false; P ⇒ Q is true in all other situations.

2.当 P 为真且 Q 为假时，P ⇒ Q 为假；在所有其他情况下，P ⇒ Q 为真。

3. The converse of P ⇒ Q is Q ⇒ P , which is not logically equivalent to P ⇒ Q . The contrapositive of P ⇒ Q is (~ Q ) ⇒ (~ P ), which is logically equivalent to P ⇒ Q . We have P ⇒ Q ≡ (~ P )∨ Q , and hence ∼ ( P ⇒ Q ) ≡ P ∧ ( ∼ Q ) .

3. P ⇒ Q 的逆命题是 Q ⇒ P，它与 P ⇒ Q 逻辑不等价。P ⇒ Q 的逆否命题是 (~Q) ⇒ (~P)，它与 P ⇒ Q 逻辑等价。我们有 P ⇒ Q ≡ (~P)∨Q，因此 ∼(P⇒Q)≡P∧(∼Q)。

Exercises

练习

1. Make a truth table for each propositional form.

1. 为每个命题形式制作真值表。

(a) ( P ∨(~ Q )) ⇒ P (b) P ⇒ ( Q ∧ ( ∼ P ) ) (c) ( P ⊕ Q ) ⇒ ( P ∨ Q ) .

(a) (P∨(~Q)) ⇒ P (b) P⇒(Q∧(∼P)) (c) (P⊕Q)⇒(P∨Q).

2. Make a truth table for each propositional form.

2.为每个命题形式制作真值表。

(a) ( P ⇒ Q ) ∧ ( Q ⇒ R ) (b) ( P ⇒ Q ) ⇒ ( Q ∨ R ) (c) ( ∼ ( P ⊕ Q ) ) ⇒ ( ∼ ( R ∧ P ) ) .

（a）(P⇒Q)∧(Q⇒R) （b）(P ⇒ Q) ⇒ (Q∨R) （c）(∼(P⊕Q))⇒(∼(R∧P))。

3. Prove the negation laws ~(~ P ) ≡ P and ∼ ( P ∧ Q ) ≡ ( ∼ P ) ∨ ( ∼ Q ) using truth tables.

3.利用真值表证明否定定律~(~P)≡P和∼(P∧Q)≡(∼P)∨(∼Q)。

4. Use truth tables to prove the commutative laws for ∧ , ∨, and ⊕ in the Theorem on Logical Equivalences.

4.利用真值表证明逻辑等价定理中∧、∨和⊕的交换律。

5. Prove the associative laws for ∧ and ∨.

5.证明∧和∨的结合律。

6. Prove the absorption laws in part (e) of the Theorem on Logical Equivalences.

6.证明逻辑等价定理（e）部分中的吸收定律。

7. Prove the distributive laws in part (c) of the Theorem on Logical Equivalences.

7.证明逻辑等价定理（c）部分中的分配律。

8. Prove or disprove: ( ∼ P ) ⊕ ( Q ⊕ P ) ≡ ( ∼ Q ) .

8.证明或反驳：(∼P)⊕(Q⊕P)≡(∼Q)。

9. True or false?

9.对还是错？

(a) If Mars is a planet, then 2 + 2 = 4.

（a）如果火星是行星，那么 2 + 2 = 4。

(b) If 2 · 2 ≠ 4, then π is negative.

（b）如果 2 · 2 ≠ 4，则 π 为负数。

(d) If Paris is a city, then Europe is an ocean.

（d）如果巴黎是一座城市，那么欧洲就是一片海洋。

(d) If 0 = 0, then 5 is even.

（d）如果 0 = 0，那么 5 是偶数。

(e) If some trees have roots, then all crows are white.

（e）如果有些树有根，那么所有的乌鸦都是白色的。

(f) If 3 + 3 ≠ 6, then ∫ 0 ∞ 1 x 4 + 1 d x = π 2 / 4 .

（f）如果 3 + 3 ≠ 6，则 ∫0∞1x4+1dx=π2/4。

(g) If 1 + 1 = 3, then 1 + 1 = 2, but the converse is false.

（g）如果 1 + 1 = 3，则 1 + 1 = 2，但反过来不成立。

10. Assume P is a true proposition, Q is a false proposition, and R is an arbitrary proposition. Say as much as you can about the truth or falsehood of each proposition below.

10. 假设 P 为真命题，Q 为假命题，R 为任意命题。请尽可能详细地说明以下每个命题的真假。

(a) P ⇒ R (b) Q ⇒ R (c) R ⇒ P (d) R ⇒ Q (e) R ⇒ R (f) R ⇒ (~ R ).

（a）P ⇒ R （b）Q ⇒ R （c）R ⇒ P （d）R ⇒ Q （e）R ⇒ R （f）R ⇒ (~R)。

11. Let x ₀ be a fixed integer, and let P be the statement:

11.设 x ₀ 为一个固定的整数，P 为以下语句：

“if x ₀ is even and x ₀ is prime, then x ₀ = 2.”

“如果 x ₀ 是偶数且 x ₀ 是质数，则 x ₀ = 2。”

(a)Write the converse of P .

（a）写出 P 的逆问题。

(b)Write the contrapositive of P .

（b）写出P的逆否命题。

(c)Write the converse of the contrapositive of P .

（c）写出命题 P 的逆否命题的逆命题。

(d)Suppose x ₀ is 8. Is P true or false? What about the converse of P ?

(d)假设x ₀ 为8。P为真还是假？P的逆命题呢？

12. The inverse of P ⇒ Q is defined to be (~ P ) ⇒ (~ Q ). Decide whether the inverse of P ⇒ Q is logically equivalent to: (a) P ⇒ Q ; (b) the converse of P ⇒ Q ; (c) the contrapositive of P ⇒ Q .

12. P ⇒ Q 的逆命题定义为 (~P) ⇒ (~Q)。判断 P ⇒ Q 的逆命题是否逻辑等价于：(a) P ⇒ Q；(b) P ⇒ Q 的逆命题；(c) P ⇒ Q 的逆否命题。

13. Write the converse and the contrapositive of each statement.

13.写出下列各命题的逆命题和逆否命题。

(a)If f is continuous or monotonic, then f is integrable.

（a）如果 f 是连续的或者单调的，那么 f 是可积的。

(b)If g is not continuous, then g is not differentiable.

（b）如果 g 不连续，则 g 不可微。

(c)If p is prime, then if p is even, then p = 2.

（c）如果 p 是质数，那么如果 p 是偶数，那么 p = 2。

14. Use known logical equivalences to show that ( P ∧ R ) ⇒ ( ∼ Q ) is logically equivalent to ∼ ( P ∧ ( Q ∧ R ) ) without making a truth table.

14.利用已知的逻辑等价关系证明 (P∧R)⇒(∼Q) 与 ∼(P∧(Q∧R)) 逻辑等价，而不列出真值表。

15. (a) Use known logical equivalences to show that P ⇒ ( Q ⇒ R ) is logically equivalent to ( P ∧ Q ) ⇒ R without making a truth table. (b) Is ( P ⇒ Q ) ⇒ R logically equivalent to P ⇒ ( Q ⇒ R )? Explain.

15.(a) 利用已知的逻辑等价关系，证明 P ⇒ (Q ⇒ R) 与 (P∧Q) ⇒ R 逻辑等价，无需列出真值表。(b) (P ⇒ Q) ⇒ R 与 P ⇒ (Q ⇒ R) 逻辑等价吗？请解释。

16. Write the converse of ( P ⇒ Q ) ⇒ R and the contrapositive of ( P ⇒ Q ) ⇒ R .

16.写出 (P ⇒ Q) ⇒ R 的逆命题和 (P ⇒ Q) ⇒ R 的逆否命题。

17. Use the Theorem on IF to replace each propositional form with an equivalent form that does not use ⇒.

17.利用 IF 定理，将每个命题形式替换为不使用 ⇒ 的等价形式。

( P ∧ Q ) ⇒ ( R ∨ S ) (b) P ⇒ ((~ Q ) ⇒ P ) (c) [ P ⇒ ( Q ⇒ R )] ⇒ [( P ⇒ Q ) ⇒ ( P ⇒ R )]

(P∧Q)⇒(R∨S) (b) P ⇒ ((~Q) ⇒ P) (c) [P ⇒ (Q ⇒ R)] ⇒ [(P ⇒ Q) ⇒ (P ⇒ R)]

18. Which proposed distributive laws are correct? Prove your answers.

18.哪些分配律是正确的？请证明你的答案。

(a) P ∨ ( Q ⊕ R ) ≡ ( P ∨ Q ) ⊕ ( P ∨ R ) .

（a）P∨(Q⊕R)≡(P∨Q)⊕(P∨R)。

(b) P ⇒ ( Q ∧ R ) ≡ ( P ⇒ Q ) ∧ ( P ⇒ R ) .

(b)P⇒(Q∧R)≡(P⇒Q)∧(P⇒R)。

(c) P ⇒ ( Q ∨ R ) ≡ ( P ⇒ Q )∨( P ⇒ R ).

（c）P ⇒ (Q∨R) ≡ (P ⇒ Q)∨(P ⇒ R)。

(d) P ⇒ ( Q ⊕ R ) ≡ ( P ⇒ Q ) ⊕ ( P ⇒ R ) .

（d）P⇒（Q⊕R）≡（P⇒Q）⊕（P⇒R）。

(e) P ∧ ( Q ⇒ R ) ≡ ( P ∧ Q ) ⇒ ( P ∧ R ) .

(e)P∧(Q⇒R)=(P∧Q)⇒(P∧R)。

(d) P ∨( Q ⇒ R ) ≡ ( P ∨ Q ) ⇒ ( P ∨ R ).

（d）P∨(Q ⇒ R) ≡ (P ∨ Q) ⇒ (P∨R)。

(g) P ⊕ ( Q ⇒ R ) ≡ ( P ⊕ Q ) ⇒ ( P ⊕ R ) .

(g)P⊕(Q⇒R)≡(P⊕Q)⇒(P⊕R)。

19. Prove A ∧ ( B ∨ C ∨ D ∨ E ) ≡ ( A ∧ B ) ∨ ( A ∧ C ) ∨ ( A ∧ D ) ∨ ( A ∧ E ) without using truth tables.

19. 不使用真值表证明 A∧(B∨C∨D∨E)≡(A∧B)∨(A∧C)∨(A∧D)∨(A∧E)。

20. Use logical equivalences from this section to find four different IF-statements that are logically equivalent to (~ P )∨(~ Q )∨ R .

20.利用本节中的逻辑等价性，找出四个与 (~P)∨(~Q)∨R 逻辑等价的不同 IF 语句。

21. The FOIL Rule in algebra says that for all real numbers a , b , c , d , ( a + b ) · ( c + d ) = ( ac + ad ) + ( bc + bd ). (a) Prove this rule using laws of algebra. (b) Formulate three analogous FOIL rules for logical connectives, and prove these rules without truth tables using the Theorem on Logical Equivalences.

21. 代数中的 FOIL 法则指出，对于任意实数 a、b、c、d，(a + b) · (c + d) = (ac + ad) + (bc + bd)。(a) 用代数定律证明该法则。(b) 为逻辑连接词构造三个类似的 FOIL 法则，并利用逻辑等价定理在不使用真值表的情况下证明这些法则。

22. Use known logical equivalences (not truth tables) to prove: ( A ⇒ B ) ∧ ( C ⇒ D ) ≡ ( ∼ ( A ∨ C ) ) ∨ ( A ⇒ D ) ∨ ( C ⇒ B ) ∨ ( B ∧ D ) .

22.使用已知的逻辑等价关系（而不是真值表）证明：(A⇒B)∧(C⇒D)≡(∼(A∨C))∨(A⇒D)∨(C⇒B)∨(B∧D)。

23. True or false? Explain.

23.判断题：对还是错？请解释。

(a) The contrapositive of P ⇒ Q always has the same truth value as P ⇒ Q .

（a）P ⇒ Q 的逆否命题总是与 P ⇒ Q 具有相同的真值。

(b) The converse of P ⇒ Q always has the same truth value as the negation of P ⇒ Q .

（b）P ⇒ Q 的逆命题与 P ⇒ Q 的否定命题的真值总是相同的。

(c) If P ⇒ Q is false, then the converse must be true.

（c）如果 P ⇒ Q 为假，那么其逆命题必定为真。

(d) If P ⇒ Q is true, then the converse must be true.

（d）如果 P ⇒ Q 为真，那么其逆命题也必定为真。

(e) If the hypothesis and conclusion of a conditional statement have the same truth value, then the conditional statement must be true.

（e）如果一个条件语句的假设和结论具有相同的真值，那么这个条件语句必然为真。

24. Give specific examples of propositional forms A and B with each property below. Explain why your examples work. (a) A ∨ B is logically equivalent to A ⊕ B . (b) A ⇒ B ≡ B ⇒ A , but A ⇒ B ≢ A ∧ B . (c) A ∨ B is logically equivalent to ∼ ( A ∧ B ) .

24. 请给出命题形式 A 和 B 的具体例子，并解释以下每个性质为何成立。(a) A∨B 逻辑等价于 A⊕B。(b) A⇒B≡B⇒A，但 A⇒B≢A∧B。(c) A∨B 逻辑等价于 ∼(A∧B)。

25. Prove that logical equivalence of propositional forms is reflexive and transitive, as stated in (1.4) .

25.证明命题形式的逻辑等价性是自反的和传递的，如（1.4）所述。

26. Prove the substitution rules for propositional forms given in Remark 5 on page 14.

26.证明第 14 页备注 5 中给出的命题形式的替换规则。

Translations of P ⇒ Q

P ⇒ Q 的翻译

The most straightforward English translation of the propositional form P ⇒ Q is “if P , then Q .” However, there are many other English phrases with the same logical meaning as P ⇒ Q . We begin by considering some translations of IF that often cause trouble. By definition:

命题形式 P ⇒ Q 最直接的英文翻译是“如果 P，那么 Q”。然而，还有许多其他英文短语与 P ⇒ Q 具有相同的逻辑含义。我们首先来探讨一些经常引起问题的“如果”的翻译。根据定义：

• P if Q means Q ⇒ P .

•PifQ 表示 Q⇒P。

• P only if Q means P ⇒ Q .

•P仅当Q意味着P⇒Q时。

The phrase “ P if Q ” is obtained by changing the order of the clauses in “if Q then P .” In both phrases, the proposition Q immediately follows the word IF, so Q is the hypothesis and P is the conclusion of the conditional statement. However, replacing IF by ONLY IF changes the meaning: in the sentence “ P only if Q ,” P is the hypothesis and Q is the conclusion! We explain this counterintuitive phenomenon through an example. Suppose a professor says to a student, “You will pass my class ONLY IF you take the final exam.” This statement means the same thing as, “If you do not take the final exam, then you will not pass the class.” We recognize this as the contrapositive of the statement, “If you pass the class, then you took the final exam.” The same reasoning holds in general: “ P only if Q ” really means “if Q is not true, then P is not true,” which can be encoded as (~ Q ) ⇒ (~ P ). This is the contrapositive of P ⇒ Q , so this statement is logically equivalent to P ⇒ Q .

“P 如果 Q”这句话是通过改变“如果 Q 那么 P”中子句的顺序得到的。在这两个短语中，命题 Q 都紧跟在“如果”之后，因此 Q 是条件语句的假设，P 是结论。然而，如果将“如果”替换为“仅当”，意思就发生了变化：在“P 仅当 Q”这句话中，P 变成了假设，Q 变成了结论！我们用一个例子来解释这种反直觉的现象。假设一位教授对学生说：“你只有参加期末考试才能通过我的课。”这句话的意思与“如果你不参加期末考试，那么你就不会通过这门课”相同。我们将其视为“如果你通过了这门课，那么你参加了期末考试”的逆否命题。同样的道理也适用于一般情况：“P 仅当 Q”实际上意味着“如果 Q 不为真，那么 P 也不为真”，这可以编码为 (~Q) ⇒ (~P)。这是 P ⇒ Q 的逆否命题，因此该命题在逻辑上等价于 P ⇒ Q。

Now consider the meaning of the words NECESSARY and SUFFICIENT. By definition:

现在来思考一下“必要”和“充分”这两个词的含义。根据定义：

• P is sufficient for Q means P ⇒ Q .

•P 足以满足 Q 意味着 P⇒Q。

• P is necessary for Q means Q ⇒ P .

•P 是 Q 所必需的，意味着 Q⇒P。

For example, “Differentiability of f is sufficient for continuity of f ” means “If f is differentiable, then f is continuous.” On the other hand, the word NECESSARY (like the word ONLY) has a hidden negating effect. The statement “Taking the final exam is necessary for passing the course” means, “If you do not take the final exam, then you will not pass the course,” which in turn has the same meaning as, “If you pass the course, then you took the final exam.” In general, saying “ P is necessary for Q ” means that if P does NOT hold, then Q does NOT hold, which can be encoded as (~ P ) ⇒ (~ Q ). This is the contrapositive of Q ⇒ P , so this statement has the same logical meaning as Q ⇒ P .

例如，“f 的可微性是 f 连续性的充分条件”意味着“如果 f 可微，则 f 连续”。另一方面，“必要”（如同“唯一”）一词具有隐含的否定作用。“参加期末考试是课程及格的必要条件”意味着“如果你不参加期末考试，那么你就不会通过这门课程”，这与“如果你通过了这门课程，那么你参加了期末考试”的含义相同。一般来说，“P 是 Q 的必要条件”意味着如果 P 不成立，则 Q 也不成立，这可以编码为 (~P) ⇒ (~Q)。这是 Q ⇒ P 的逆否命题，因此该语句与 Q ⇒ P 具有相同的逻辑含义。

One way to remember the correct meaning of NECESSARY is to note that “ P is necessary for Q ” is the converse of “ P is sufficient for Q .” Similarly, “ P only if Q ” is the converse of “ P if Q .” We must take care, however, because the passive voice (and similar constructions that change the order of phrases in a sentence) can reverse the positions of P and Q . For example, all of the following phrases can be used to translate P ⇒ Q :

记住“NECESSARY”正确含义的一个方法是注意到“P是Q的必要条件”是“P是Q的充分条件”的逆句。类似地，“P仅当Q”是“P当Q”的逆句。但是，我们必须注意，因为被动语态（以及其他改变句子中短语顺序的类似结构）可能会颠倒P和Q的位置。例如，以下所有短语都可以用来翻译为P ⇒ Q：

Notice the key preposition FOR, which can help you locate the correct hypothesis and conclusion in each phrase. Yet other possible translations of P ⇒ Q include:

注意关键介词 FOR，它可以帮助你在每句话中找到正确的假设和结论。P ⇒ Q 的其他可能翻译包括：

In particular, when reading a form such as P ⇒ Q aloud, you may read the symbol ⇒ as the word IMPLIES. But it is wrong to read ⇒ as the word IF, since “ P if Q ” means Q ⇒ P , not P ⇒ Q . It is correct, but potentially confusing, to pronounce the symbol ⇒ as ONLY IF. My personal recommendation is to read P ⇒ Q as “if P , then Q .” But you must still be familiar with all of the variants above, since they occur frequently in mathematical writing.

特别是，在朗读 P ⇒ Q 这类表达式时，你可能会把符号 ⇒ 读作“暗示”（IMPLIES）。但把 ⇒ 读作“如果”（IF）是错误的，因为“P 如果 Q”的意思是 Q ⇒ P，而不是 P ⇒ Q。把符号 ⇒ 读作“仅当”（ONLY IF）是正确的，但可能会造成混淆。我个人建议把 P ⇒ Q 读作“如果 P，那么 Q”。但你仍然需要熟悉以上所有变体，因为它们在数学写作中经常出现。

While we are discussing translation issues, we should mention the logical meaning of a few other common English phrases:

在讨论翻译问题时，我们应该提及一些其他常用英语短语的逻辑含义：

The words BUT and ALTHOUGH suggest some kind of contrast between the two clauses joined by these words, but this contrast is ignored in logic. For logical purposes, BUT and ALTHOUGH (and BOTH) have exactly the same meaning as AND.

“但是”和“虽然”这两个词暗示着它们所连接的两个分句之间存在某种对比，但在逻辑中，这种对比会被忽略。从逻辑角度来看，“但是”和“虽然”（以及“两者”）与“并且”的含义完全相同。

There are some other English phrases whose mathematical meaning does not seem to be completely standardized. I assert that “either P or Q ” means P ∨ Q (inclusive-OR), “ P provided that Q ” means Q ⇒ P , and “ P unless Q ” means P ∨ Q , but not all mathematical writers agree with these conventions.

还有一些英语短语的数学含义似乎尚未完全标准化。我认为“either P or Q”表示 P ∨ Q（包含或），“P provided that Q”表示 Q ⇒ P，“P unless Q”表示 P ∨ Q，但并非所有数学家都认同这些约定。

What IFF Means

IFF是什么意思

Now that we understand IF and its many synonyms, it is time to define the related logical connective IFF (pronounced “if and only if” and symbolized by ⇔). The formal definition of this word appears in the truth table below.

现在我们已经了解了 IF 及其众多同义词，接下来需要定义相关的逻辑连接词 IFF（读作“如果且仅当”，符号为 ⇔）。该词的正式定义如下表所示。

As with previous theorems, we prove these logical equivalences with truth tables. As a sample, we prove parts (a) and (e) as shown:

与之前的定理一样，我们用真值表证明这些逻辑等价性。例如，我们证明 (a) 和 (e) 部分，如下所示：

Columns 3 and 6 agree, proving (a); columns 3 and 9 agree, proving (e).

第 3 列和第 6 列一致，证明了 (a)；第 3 列和第 9 列一致，证明了 (e)。

Regarding (b), note that “ P if and only if Q ” is short for “ P if Q , and P only if Q ,” which translates to ( Q ⇒ P ) ∧ ( P ⇒ Q ) . We know this is equivalent to P ⇔ Q by part (a) of the theorem and commutativity of ∧ . A similar analysis applies to the phrases “necessary and sufficient” and “when and only when.”

关于 (b)，请注意，“P 当且仅当 Q”是“P 如果 Q，且 P 仅当 Q”的简写，即 (Q⇒P)∧(P⇒Q)。根据定理的 (a) 部分以及 ∧ 的交换律，我们知道这等价于 P ⇔ Q。类似的分析也适用于“必要且充分”和“当且仅当”。

From part (e) of the Theorem on IFF, negating both sides of an IFF-statement does not deny the entire statement, but actually produces a logically equivalent statement. To deny an IFF-statement, we must replace the IFF by XOR, as stated in part (d) of the theorem. By negating each side of the equivalences in the Theorem on IFF, or by constructing more truth tables, we obtain the following equivalences for XOR.

根据因果相合定理的 (e) 部分，否定一个因果相合命题的两侧并不能否定整个命题，而是会产生一个逻辑等价的命题。要否定一个因果相合命题，我们必须用异或运算替换它，正如定理的 (d) 部分所述。通过否定因果相合定理中等价关系的每一侧，或者构造更多的真值表，我们可以得到以下异或运算的等价关系。

Tautologies and Contradictions

同义反复和矛盾

Certain propositional forms, called tautologies and contradictions, play a special role in logic and proofs. These are defined as follows.

某些命题形式，称为重言式和矛盾式，在逻辑和证明中扮演着特殊角色。它们的定义如下。

Note that most propositional forms have a mixture of true and false outputs, so most propositional forms are neither tautologies nor contradictions .

请注意，大多数命题形式都有真假混合的输出，因此大多数命题形式既不是重言式也不是矛盾式。